COMMENT ⊗   VALID 00002 PAGES
C REC  PAGE   DESCRIPTION
C00001 00001
C00002 00002	What we propose to do now  is look very hard at the intuituve
C00015 ENDMK
C⊗;
What we propose to do now  is look very hard at the intuituve
process of function evaluation.  Why? First in an abstract sense,
that is the business of programming languages--evaluation of functions.
They aren't called procedure-oreinted languages forr nothing!  Also
function evaluation is a basic tool of evaluation of LISP functions.
In fact a very general kind of evaluation process isgoing on in LISP,
that is evaluation of recursive functions.  Later we will
study the mechanisms which will support recursive evaluation

    First, as we mentioned in regard to the polynomial arithmetic
examples the intuitive mathematical operations say nothing about the process
of evaluation.  (2*3) + (5*6) evaluates to 36 regardless
of whether you evaluate 2*3 first or 5*6 first, or whether you do them in parallel.
Probably if one were forced to explicate mathematical
evaluation, we would have to say parallel evaluation.

     Already in conditional expressions we have seen that order of 
evaluation makes a difference, and certainly when we try to mechanize
function evaluation on a sequential machine we WILL have to choose
SOME order of evaluation.  We must also make some decision regarding
the order of evaluation of the arguments to a function call,
say f[x1,x2,...xn).  We willl assume that we will evaluate the arguments
from left to right.  The evaluation scheme which we choose
is called inside-out or call-by-value.  Alternative proposals exist
and have their merits;  call-by-name (outside-in) evaluation is another
well-known scheme.  Intuitively, call by value says:
evaluate the arguments to a function before you attempt to apply the arguments 
to the function definition.  Here are some examples:
   Let f[x,y]  be x↑2 + y and consider f[3+4; 2*2].  Then
call-by-value says evaluate the arguments (7 and 4) associate those
with the formal parameters of f(i.e. x:7 ;y:4) and evaluate the body of
f(i.e. 7↑2 + 4 = 57); call by name says pass the unevaluated actual 
parameters to the function, then perhaps evaluate.  I.e. (3+4)↑2 + 2*2
arises (which also evaluates to 57).  There are very simple instances
of functions such that call-by-value and call-by-name tdo not result
in the same value.  Notice that the process of evaluatioon(by value)
is recursive.  That is, it goes something like this:
If the expression to be evaluated is a constant then the value
(of the expression) is that constant.  (the value of 3 is 3).
If the expression is a variable the see what the current value associated
whith that variable is. (Within the evaluation of say
f[3;4] where f[x;y] ← x↑2 + y the current value of the variable
x is 3.)  The only other kind of expression that we can have is a function
name followed by arguments. (Say f[3;4]).  In this case we evaluate the arguments,
that is, we recur!! and then apply the defintion of the function to those
evaluated arguments.  How do you apply the evaluated arguments to the function
defintion?  You associate or bind the formal parameters( or variables)
of the definition to the actual parameters.(or evaluated arguments.)
Then you evaluate the body of the function.  Why all the emphasis 
on the mechanism of function evaluation?  For one reason implementation
of programming languages requires careful consideration of this
problem.  If you understand the formal model of LISP and the corresponding
model of implementation, you should have an exceptionally
clear picture of the problems of implementation of languages, you
will understand the problems of semantics of languages.

How do we transcribe the evaluation of arithmetic functions to LISP functions.
ItIs easy.  The only difference is that the class of constnats is larger
(than the integers)  What are the constants of LISP? They're just the Sexprs. 
(The  value of (A . B) is (A . B) ,,, just like the value of 3 is 3.)
One of the artifacts of LISP which we haven't talked about with respect to
evaluation is the conditionalexpression. But clearly its evlaution is also
recursive.

In more specific detail here is some of the structure of the
LISP evaluation mechanism:

If the expression to be evaluated is a constant then the value
is that constant.
If the expression is a conditional then it is of the form
[p1→ e1; p2→ e2; ...pn → en].  Evaluate it.
If the expression is of the form: function name followed by 
arguments then:

1. evaluate the arguments(from left to right)
2. find the definitooon of the function
3. associate thhe evaluated arguments with the formal
   parameters in the function definition
4.   evaluate the body of the function.

So we can describe the outline of the mechanical procedure which
can be used in the evaluation of LISP functions.  Recall our  discussion
of the differentiation formulas.  We describeed the mechanism of 
differentiating as a recursive process.  Then mechanized that scheme
as a LISP function, translating the polynomials to list notation,
since the domain of LISP functions is Sexprs.  We are in a parallel
situation here.  It should be clear that we could write a LISP
function representing the evaluation process provided that we caan
find a representation for LISP expressions a Sexpressions. We 
wil accomplish this by using exactly the scheme applied in transforming
the prefix notation forms of polynomals into list notation.
The great mother of all functions is exactly the evaluation mechanism for 
the LISP primitive functions and predicates, car cdr,cons, atom and eq
when restricted to functional composition and constant arguments.
The great mother revisited is the extension to conditional exprressions.
But letIs stop for some examples of translating LISP functions into Sexpr notation.

	LISP expression			translation as Sexpr
we will represent numbers just as numbers
		2				2
we will translate variavles to their upper-case counterpart
		x				X
		y2				Y2
		car				CAR

no we've got a problem: if x translates to X and since X is a LISP
expression IT must alos have a translate.  Sureyu it's translation
can't be X. (why?)  The translation scheme we pick is:
for any sexpresion y, it's translation is (QUOTE y)
		X				(QUOTE X)
		(A . B)				(QUOTE (A . B))
		QUOTE				(QUOTE QUOTE)
we already now how to translate f[x1,x2,...,xn]
		f[e1;e2; ...en]			(F e1' e2' ...en')
						where ei' is the translate of ei
		car[x]				(CAR X)
		car[X]				(CAR (QUOTE X))
		cons[cdr[(A . B)];x]		(CONS (CDR (QUOTE (A . B))) X)

what's left?   conditionals.
		[p1 → e1;...pn → en]		(COND (p1' e1) ... (pn ' en'))
		[atom[x] →1; q[y] → X]		(COND ((ATOM X) 1) ((Q Y) X))


Since T and NIL are used so frequently, we chose their
translates to be T and NIL rather than (QUOTE T) and (QUOTE NIL).
You should now go back and look at the tgm's again now that you know
what they mean.  You should note that with respect to atoms, the great
mothers are only defined for T and NIL.  Other atoms( which are
the tttanslates of variables) are not recognized and return a h.s. message.
The question of variables requires some careful study.  Before we do that,
letIs see whaat the great mother's actually accomplish.
First, tgm's explicitly tell you what the meaning of vaarious subsets
of LISP is.  That is, the tgms explicitly codify tthe semantics(or meaning)
of LISP.  Next, if you are able to code tgm on a machine, then you can
input the Sexpr form of LISP expressions and they will be evaluated for you.
Great mother does it all,,,


The part of our informal argument which is clearly missing
 in the tgms is the details of handlng variables and the names of functions.  That is,
how do we describe the binding of variables to values as a mechanical process
and given the name of a defined function, how do we get the actual definiton?
These are actually the same problem: that of symbol table manipulations.